// https://leetcode.cn/problems/duplicate-zeros/

// 题干:给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
// 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

// 示例:输入：arr = [1,0,2,3,0,4,5,0]
//      输出：[1,0,0,2,3,0,0,4]

// 碎语:只用一个指针的话，会出现数字覆盖的问题，采用双指针
//      而从左到后的话，也会出现数字覆盖的问题，所以采用从右到左的方向

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        // 先利用cur和dest指针找出最后一个需要填入数组的数
        // dest指向数字的最后一个位置，即n-1
        int dest = -1, cur = 0, n = arr.size();
        while (cur < n){
            if (arr[cur]) dest++;
            else dest += 2;

            if (dest >= n - 1) break; // 此时cur也指向了最后一个需要填入数组的数
            cur++;
        }

        // 考虑到最后一个填入数组的数如果是零的话，dest指针多走了一位，处理下这种特殊情况
        if (dest == n){
            arr[--dest] = 0;
            cur--;
            dest--;
        }

        // 开始从右往左进行复写
        while (cur >= 0){
            if (arr[cur]) arr[dest--] = arr[cur];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            cur--;
        }
    }
};

int main()
{
    Solution sol;
    vector<int> arr = {1,0,2,0,5,3,4};

    sol.duplicateZeros(arr);
    for (auto num : arr){
        cout << num << " ";
    }
    cout << endl;

    return 0;
}